The present invention relates to a simple and systematic process for constructing and coding codes which are known by the abbreviation LDPC standing for xe2x80x9cLow Density Parity Checkxe2x80x9d.
Gallager""s codes, proposed around 1963, are the progenitor of the LDPC codes currently envisaged as an alternative to turbocodes.
An article published in the IEEE journal Transaction on Information Theory, Vol. 45 No. 2, March 1999 by M. J. C. MacKay entitled xe2x80x9cGood Error Correcting Codes Based on very Sparse Matricesxe2x80x9d presents interesting results regarding these codes, in particular the fact that:
for blocks of large size, they are asymptotically xe2x80x9cvery good codesxe2x80x9d
the weighted decoding (or xe2x80x9csoft decodingxe2x80x9d or xe2x80x9cflexible decodingxe2x80x9d) is easy to implement.
However, there is no method other than heuristic for constructing them.
According to this coding technique a code (N, K) comprising N symbols, of which K are free, is defined by its parity check matrix A comprising M=Nxe2x88x92K rows and N columns.
The check matrix A is characterized by its low xe2x80x9cdensityxe2x80x9d: this should be understood to mean that it comprises a small number of nonzero elements.
More precisely, it comprises exactly t nonzero symbols in each column, all the others being equal to 0.
If the symbols of a code word are denoted ci, i=0 . . . Nxe2x88x921 and the elements of the check matrix Aij, the code satisfies M=Nxe2x88x92K relations of the form:             ∑              i        =                              0            ⁢                          xe2x80x83                        ⁢            …            ⁢                          xe2x80x83                        ⁢            N                    -          1                            xe2x80x83              ⁢          xe2x80x83        ⁢                  A        mi            ⁢              xe2x80x83            ⁢              C        i            ⁢              xe2x80x83            ⁢      for      ⁢              xe2x80x83            ⁢      m        =            0      ⁢              xe2x80x83            ⁢      …      ⁢              xe2x80x83            ⁢      M        -    1  
The methods proposed by M. J. C. MacKay consist in building an initial matrix A from smaller unit matrices or tridiagonal matrices, then in permuting their columns so as to arrive at the desired result. Experience shows, however, that it is difficult to satisfy the various constraints imposed in respect of their construction.
The aim of the invention is to alleviate the aforesaid drawbacks.
To this end the subject of the invention is a process for constructing LDPC codes comprising N symbols, of which K are free, each code being defined by a check matrix A comprising M=Nxe2x88x92K rows N columns and t nonzero symbols in each column, which process consists:
axe2x80x94in allocating the same number of nonzero symbols xe2x80x9ctxe2x80x9d to all the rows of the check matrix A,
bxe2x80x94in taking as number of symbols xe2x80x9ctxe2x80x9d the smallest possible odd number,
cxe2x80x94in defining the columns in such a way that any two columns of the check matrix A have at most only one nonzero value,
dxe2x80x94and in defining the rows in such a way that two rows of the check matrix A have only one nonzero common value.
The process according to the invention has the advantage that it makes it possible to simplify the coding and decoding algorithms by using a check matrix A having the lowest possible density whilst giving good performance for reasonable complexity, the computational power required being proportional to the number t. Insofar as there are few errors, constraint xe2x80x9ccxe2x80x9d above allows the decoding algorithm to converge in all circumstances.